package Test;

import java.util.*;

public class topic {

    public static int firstUniqChar(String str) {
        int n = str.length();
        int[] cnt = new int[26];
        for(int i = 0; i < n; i++) {
            char ch = str.charAt(i);
            ++cnt[ch-'a'];
        }
        for(int i = 0; i < n; i++) {
            char ch = str.charAt(i);
            if(cnt[ch-'a'] == 1) {
                return i;
            }
        }
        return -1;
    }


    /**
     * 前K个高频单词
     * @param
     */
    public List<String> topFrequent(String[] words,int k) {
        //1.每个单词出现的次数
        Map<String,Integer> map = new HashMap<>();
        for(String s : words) {
            if(map.get(s) == null) {
                map.put(s,1);
            }else {
                int val = map.get(s);
                map.put(s,val+1);
            }
        }
        //此时每个单词出现的次数已经统计完毕
        //2.创建小根堆（默认）
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                return o2.getValue().compareTo(o1.getValue());//根据字母顺序变成大根堆
            }
        });

        //3.此时需要遍历map
        for(Map.Entry<String,Integer> entry : map.entrySet()) {
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            }else {
                Map.Entry<String,Integer> top = minHeap.peek();
                if(top.getValue().compareTo(entry.getValue()) == 0) {
                    //频率相同的情况下，判断key值，key小的入
                    if(top.getKey().compareTo(entry.getKey()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else {
                    if (top.getValue().compareTo(entry.getValue()) < 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        //4.接下来，要把小根堆里面的k个元素取出来，放到一个集合里面，然后逆置（因为小根堆堆顶是最小元素）
        List<String> ret = new ArrayList<>();
        for(int i =0; i < k; i++) {
            String s = minHeap.poll().getKey();
            ret.add(s);
        }
        Collections.reverse(ret);
        return ret;

    }

    /**
     * 统计每个数字出现的次数
     * @param array
     */
    public static void func2(int[] array) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0 ; i < array.length; i++) {
            //以前Map中没有这个单词
            if(map.get(array[i]) == null) {
                map.put(array[i],1);
            }else {
                //在Map中之前出现过
                int val = map.get(array[i]);
                map.put(array[i],val+1);
            }
        }
        System.out.println(map);
    }

    public static void main(String[] args) {
        String s1 = "hello";
        String s2 = "hello";
        String s3 = new String("hello");
        String s4 = new String("hello");
        System.out.println(s1 == s2); //true
        System.out.println(s2 == s3); //false
        System.out.println(s3 == s4); //false
    }

    public static void main2(String[] args) {
        int[] array = { 1,2,3,2,1,2,1};
        func2(array);
    }
    public static void main1(String[] args) {
        String strings = "loveleetcode";
        System.out.println(firstUniqChar(strings));
    }
}
